#include<iostream>
using namespace std;
#include<unordered_map>
#include<list>
class LRUCache {
public:
    LRUCache(int capacity)
        :cap(capacity)
    {}
    int get(int key) {
        if (ma.count(key)) {
            li.push_front({ key,(*ma[key]).second });
            li.erase(ma[key]);
            ma[key] = li.begin();
            return li.front().second;
        }
        return -1;
    }
    void put(int key, int value) {
        li.push_front({ key,value });
        if (ma.count(key)) {
            li.erase(ma[key]);
            ma[key] = li.begin();
            return;
        }
        ++size;
        ma[key] = li.begin();
        if (size <= cap)
            return;
        ma.erase(li.back().first);
        li.pop_back();
    }
    int cap;
    int size = 0;
    list<pair<int,int>> li;
    unordered_map<int, list<pair<int,int>>::iterator> ma;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
int main() {
    LRUCache test(2);
    test.put(1, 0);
    test.put(2, 2);
    test.get(1);
    test.put(3, 3);
    test.get(2);
    test.put(4, 4);
    test.get(1);
    test.get(3);
    test.get(4);
}